/** \file    bmpfill_impl.h
  * \brief   routins for filling areas in bitmaps.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/imglib/bmpfill_impl.h,v 1.2 2004/12/10 05:10:44 cscom1r4 Exp $
  */

#ifndef _bmpfill_impl_h_
#define _bmpfill_impl_h_

#include <vector>
#include "imglib/bitmap.h"
#include "xtd/group.h"

namespace img {

///merges every segment adjacent to frame border, that is corresponded to reset bits in 'bmp'
///\return root index of merged segment (it will be not simple-connected)
///if the border has no reset bits 'reserved' value is returned
template <class RI, class PV>
typename RI::elem_type merge_reset_border(const RI& index_map, PV& piece_vector, 
								 const bitmap &bmp, typename RI::elem_type reserved)
{
	size_t w = bmp.width(), h = bmp.height();
	assert(index_map.width() == w && index_map.height() == h);

	typedef typename RI::elem_type e;
	std::vector<e> roots;
	roots.reserve(2*(w+h)-4);

	size_t x, y;
	for (x = 0; x != w-1; ++x) {
		if (!bmp(x, 0))
			roots.push_back(xtd::find_root_idx(piece_vector, index_map(x, 0)));
		if (!bmp(x, h-1))
			roots.push_back(xtd::find_root_idx(piece_vector, index_map(x, h-1)));
	}
	if (h > 2)
		for (y = 1; y < h-2; ++y) {
			if (!bmp(0, y))
				roots.push_back(xtd::find_root_idx(piece_vector, index_map(0, y)));
			if (!bmp(w-1, y))
				roots.push_back(xtd::find_root_idx(piece_vector, index_map(w-1, y)));
		}

	if (roots.empty())
		return reserved;

	std::vector<e>::iterator i = roots.begin();
	for (++i; i != roots.end(); ++i)
		xtd::union_sets(piece_vector, roots.front(), *i);

	return xtd::find_root_idx(piece_vector, roots.front());
}

///merges any two regions whose root indeces are both not equal to 'out'
template <class RI, class PV>
void merge_internals(const RI& index_map, PV& piece_vector, typename RI::elem_type out)
{
	typedef typename RI::elem_type e;
	typename RI::const_iterator ii(index_map.begin());
	for (; ii != index_map.end(); ++ii) {
		const size_t x = ii.x(), y = ii.y();
		e r1 = xtd::find_root_idx(piece_vector, *ii);
		if (r1 == out)
			continue;
		if (x != 0) {
			e rl = xtd::find_root_idx(piece_vector, index_map(x-1,y));
			if (rl != out && rl != r1)
				r1 = xtd::link_roots2(piece_vector, rl, r1);
		}
		if (y != 0) {
			e rt = xtd::find_root_idx(piece_vector, index_map(x,y-1));
			if (rt != out && rt != r1)
				r1 = xtd::link_roots2(piece_vector, rt, r1);
		}
	}
}

///resets bits in 'bmp' whose corresponding index in index_map has given root
template <class RI, class PV>
inline void reset_segment(const RI& index_map, PV& piece_vector, 
				   typename RI::elem_type root, bitmap &bmp)
{
	typename RI::const_iterator ii(index_map.begin());
	for (; ii != index_map.end(); ++ii)
		bmp[ii] = xtd::find_root_idx(piece_vector, *ii) != root;
}

} //img

#endif //_bmpfill_impl_h_
